Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates

Abstract

We revisit Approximate Graph Propagation (AGP), a unified framework that captures various graph propagation tasks, such as PageRank, Personalized PageRank, feature propagation in Graph Neural Networks, and graph-based Retrieval-Augmented Generation. Our work focuses on the settings of dynamic graphs and dynamic parameterized queries, where the underlying graphs evolve over time (updated by edge insertions or deletions) and the input query parameters are specified on the fly to fit application needs. Our first contribution is an interesting observation that the SOTA solution, AGP-Static, can be adapted to support dynamic parameterized queries; however, several challenges remain unresolved. Fi..